package DataStructure.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 95. 不同的二叉搜索树 II https://leetcode.cn/problems/unique-binary-search-trees-ii
 * 题目简述：给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树
 */
public class GenerateTrees {

    /**
     * 思路：递归的获取从[begin, end]中任选一节点作为根节点的所有子树
     */
    public List<TreeNode> generateTrees(int n) {
        return recur(1, n);
    }

    /**
     * 递归函数体：遍历[begin, end]作为根节点，然后获取左边和右边所有可能的子树，然后和根节点组合构成当前层所有可能的子树。
     * 递归终止条件begin > end，返回List(null)
     */
    public List<TreeNode> recur(int begin, int end) {
        List<TreeNode> result = new ArrayList<>();
        if (begin > end) {
            result.add(null);
            return result;
        }
        for (int i = begin;i <= end;i++) {
            List<TreeNode> leftList = recur(begin, i-1);
            List<TreeNode> rightList = recur(i+1, end);
            for (TreeNode left : leftList) {
                for (TreeNode right : rightList) {
                    TreeNode node = new TreeNode(i);
                    node.left = left;
                    node.right = right;
                    result.add(node);
                }
            }
        }
        return result;
    }
}
